//
// Created by Administrator on 2021/7/19.
//

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxFrequency(vector<int> &nums, int k) {
        sort(nums.begin(), nums.end());
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            int times = k;
            int j = i - 1;
            while (times > 0 and j >= 0) {
                times -= (nums[i] - nums[j]);
                --j;
            }
            if (times < 0) ++j;
            ans = max(ans, i - j);
        }
        return ans;
    }

    // 超时
    int maxFrequency2(vector<int> &nums, int k) { // 题解 滑动窗口
        /**
         * 每次右移一位，需要增加(right - left) * (nums[right] - nums[right -1])这么多数字。
         */
        sort(nums.begin(), nums.end());
        int n = (int) nums.size();
        long long total = 0;
        int l = 0, res = 1;
        for (int r = 1; r < n; ++r) {
            total += (long long) (nums[r] - nums[r - 1]) * (r - l);
            while (total > k) {
                total -= nums[r] - nums[l];
                ++l; // 移动左边界
            }
            res = max(res, r - l + 1);
        }
        return res;

    }
};

int main() {
    vector<int> nums{3, 9, 6};
    Solution solution;
    cout << solution.maxFrequency2(nums, 2);
    return 0;
}